import java.util.Arrays;

/**
 * @Desc 优化后的归并排序法
 */
public enum MergeSort2 implements Sort {
    INSTANCE;

    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 一旦把递归函数的宏观语义定义下来之后，就完全可以把这个递归函数本身看成是另外一个函数
     * 这个函数可以做一些事情，并不需要把递归函数想象的那么特殊
     *
     * @param arr
     * @param l
     * @param r
     * @优化思路 1： 如果arr[mid]< arr[mid+1] 则表示arr已经有序了
     */
    private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return; //求解最基本的问题
//        int mid = (l + r) / 2; //有可能整型溢出
        int mid = l + (r - l) / 2;
        //对arr[l,mid]进行排序
        sort(arr, l, mid);//把原问题转化成更小的问题
        //对arr[mid+1,r]进行排序
        sort(arr, mid + 1, r);
        //对arr[l,mid]和arr[mid+1,r]
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r);
        }
    }

    /**
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @param <E>
     * @Desc 合并两个有序的区间 arr[l..mid] 和 arr[mid+1,r]
     */
    private <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {


        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;

        //每轮为arr[k]进行赋值
        for (int k = l; k <= r; k++) {
            //arr[i]和arr[j],在取出这两个索引之前要判断这两个索引有没有越界
            if (i > mid) {
                arr[k] = temp[j - l];
                j++;
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }

    }

    public <E extends Comparable<E>> void printArr(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
    }

    public static void main(String[] args) {
        Integer arr[] = new Integer[]{2, 6, 8, 7, 4, 3, 5, 1};
        MergeSort2 mergeSort = MergeSort2.INSTANCE;
        mergeSort.printArr(arr);
        mergeSort.sort(arr);
        mergeSort.printArr(arr);

    }

}
